package greedy;

/**
 * @Author: 海琳琦
 * @Date: 2022/2/27 14:36
 * 跳跃游戏 II
 */
public class Jump {

    /**
     * 贪心：局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一，再挑距离终点最近的走。
     * 整体最优：一步尽可能多走，从而达到最小步数。
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        int curDistance = 0;
        int nextDistance = 0;
        int step = 0;
        for (int i = 0; i < nums.length; i++) {
            nextDistance = Math.max(i + nums[i], nextDistance);
            if (i == curDistance) {
                if (i != nums.length - 1) {
                    step++;
                    //nextDistance一定大于curDistance（因为一定能到达终点）
                    curDistance = nextDistance;
                }
            }
            //i > curDistance时，一步走完
        }
        return step;
    }

    /**
     * 贪心：局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一，再挑距离终点最近的走。
     * 整体最优：一步尽可能多走，从而达到最小步数。
     * @param nums
     * @return
     */
    public int jump1(int[] nums) {
        int curDistance = 0;
        int nextDistance = 0;
        int step = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            nextDistance = Math.max(i + nums[i], nextDistance);
            if (i == curDistance) {
                step++;
                //nextDistance一定大于curDistance（因为一定能到达终点）
                curDistance = nextDistance;
            }
            //i > curDistance时，一步走完
        }
        return step;
    }

    public static void main(String[] args) {

    }
}
